/**
 * https://leetcode-cn.com/problems/unique-paths/
 * 不同路径
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
 * @param m 
 * @param n 
 */
 const uniquePaths = (m: number, n: number): number => {
    // dp[i] 表示到n行 i列 的方案数
    // dp[i] = dp[i] + dp[i - 1]
    // 初始值为0
    const dp: number[] = new Array(n).fill(0)

    for (let i = 0; i < m; i++) {
        dp[0] = 1 // 默认第一行的开头都是只有一种走法
        for (let j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1]
        }
    }

    return dp[n - 1]
};


// error
const uniquePaths_ERROR = (m: number, n: number): number => {
    let ans = 0

    const dfs = (row: number, col: number) => {
        // 边界判断
        if (row < 0 || col < 0) return;

        if ((row | col) === 0) {
            ans++;
            return;
        }

        // 向下移动
        dfs(row - 1, col)

        // 向右移动
        dfs(row, col - 1)
    }

    // 要从下标 - 1开始
    dfs(m - 1, n - 1)

    return ans
};

// console.log(uniquePaths(19, 13))
console.log(uniquePaths(3, 2))
console.log(uniquePaths(3, 7))
// console.log(uniquePaths2(3, 2))